#include<bits/stdc++.h>
using namespace std;
const int MAXN=110,MAXM=1010,MOD=31011;
int n,m,fa[MAXN],siz[MAXN];
struct edge
{
	int u,v,w,val;
}e[MAXM];
struct count
{
	int l,r,use;
}c[MAXM];
bool cmp(edge a,edge b)
{
	return a.val<b.val;
}
int getfa(int x)
{
	return fa[x]==x?x:getfa(fa[x]);
}
void link(int u,int v)
{
	if(siz[u]>siz[v])
	{
		fa[v]=u;
		siz[u]+=siz[v];
	}
	else
	{
		fa[u]=v;
		siz[v]+=siz[u];
	}
}
bool Kruskal()
{
	int cnt=0;
	for(int i=1;i<=m;++i)
	{
		int a=getfa(e[i].u),b=getfa(e[i].v);
		if(a==b)continue;
		link(a,b);
		++c[e[i].w].use;
		if(++cnt==n-1)return true;
	}
	return false;
}
int dfs(int w,int i,int k)
{
	if(k==c[w].use)return 1;
	if(i>c[w].r)return 0;
	int ans=0,a=getfa(e[i].u),b=getfa(e[i].v);
	if(a!=b)
	{
		link(a,b);
		ans=dfs(w,i+1,k+1);
		fa[a]=a;fa[b]=b;
	}
	return ans+dfs(w,i+1,k);
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)
	{
		fa[i]=i;
		siz[i]=1;
	}
	for(int i=1;i<=m;++i)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		e[i]=(edge){x,y,0,z};
	}
	sort(e+1,e+1+m,cmp);
	int w=0;
	for(int i=1;i<=m;++i)
	{
		if(e[i].val==e[i-1].val)e[i].w=w;
		else
		{
			c[w].r=i-1;
			e[i].w=++w;
			c[w].l=i;
		}
	}
	c[w].r=m;
	int ans=Kruskal();
	for(int i=1;i<=n;++i)
	{
		fa[i]=i;
		siz[i]=1;
	}
	for(int i=1;i<=w;++i)
	{
		ans=ans*dfs(i,c[i].l,0)%MOD;
		for(int j=c[i].l;j<=c[i].r;++j)
		{
			int a=getfa(e[j].u),b=getfa(e[j].v);
			if(a!=b)link(a,b);
		}
	}
	printf("%d\n",ans);
	return 0;
}
